#include <functional>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>
using namespace std;

// 1-----距离
namespace YTQ {
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first, InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for (; first != last; ++first)
        ++n;
    return n;
}
template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first, RandomAccessIterator last,
          random_access_iterator_tag) {
    return last - first;
}
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
    typedef typename iterator_traits<InputIterator>::iterator_category cgy;
    return _distance(first, last, cgy());
}

// 2-----前进
template <class InputIterator, class Distance>
inline void _advance(InputIterator& first, Distance n, input_iterator_tag) {
    while (n--)
        ++first;
}
template <class BidirectionalIterator, class Distance>
inline void _advance(BidirectionalIterator& first, Distance n,
                     bidirectional_iterator_tag) {
    if (n >= 0) {
        while (n--)
            ++first;
    } else {
        while (n++)
            --first;
    }
}
template <class RandomAccessIterator, class Distance>
inline void _advance(RandomAccessIterator& first, Distance n,
                     random_access_iterator_tag) {
    first += n;
}
template <class InputIterator, class Distance>
inline void advance(InputIterator& first, Distance n) {
    return _advance(
        first, n, typename iterator_traits<InputIterator>::iterator_category());
}

// valuetype
template <class Iter>
inline typename iterator_traits<Iter>::value_type* value_type(const Iter&) {
    return static_cast<typename iterator_traits<Iter>::value_type*>(0);
}
// 3-----copy
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result) {
    while (first != last) {
        *result = *first;
        ++first;
        ++result;
    }
    return result;
}

// 4-----destroy
template <class FI> inline void destroy(FI first, FI last) {}
// 5-----_-unique_copy
template <class InputIterator, class OutputIterator>
inline OutputIterator __unique_copy(InputIterator frist, InputIterator last,
                                    OutputIterator result,
                                    output_iterator_tag) {
    auto value = *frist;
    *result = value;
    while (++frist != last) {
        if (value != *frist) {
            value = *frist;
            *++result = value;
        }
    }
    return ++result;
}
// 5-----_-unique_copy
template <class InputIterator, class OutputIterator>
inline OutputIterator __unique_copy(InputIterator frist, InputIterator last,
                                    OutputIterator result,
                                    forward_iterator_tag) {
    *result = *frist;
    while (++frist != last) {
        if (*result != *frist) {
            *++result = *frist;
        }
    }
    return ++result;
}
// 6------find
template <class InputIterator, class T>
inline InputIterator find(InputIterator first, InputIterator last,
                          const T& value) {
    while (first != last && value != *first) {
        ++first;
    }
    return first;
}
// 7-----reverse_copy
template <class BidirectionIterator, class OutputIterator>
inline OutputIterator reverse_copy(BidirectionIterator first,
                                   BidirectionIterator last,
                                   OutputIterator result) {
    while (first != last) {
        --last;
        *result = *last;
        ++result;
    }
    return result;
}
// 8-----count_if
template <class InputIterator, class UnaryPredicate>
inline typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, UnaryPredicate pred) {
    typename iterator_traits<InputIterator>::difference_type ret = 0;
    while (first != last) {
        if (pred(*first))
            ++ret;
        ++first;
    }
    return ret;
}
// 9-----accumulate
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
    for (; first != last; ++first) {
        init += *first;
    }
    return init;
}
template <class InputIterator, class T, class BinaryPredicate>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryPredicate pred) {
    for (; first != last; ++first) {
        init = pred(init, *first);
    }
    return init;
}
int myAccumulateFunc(int x, int y) { return x + y * 10; }
struct myAccumulateClass {
    int operator()(int x, int y) { return x + y * 20; }
};
// 10-----minus
template <class T> struct minus : public binary_function<T, T, T> {
    T operator()(const T& x, const T& y) const { return x - y; }
};
// 11-----for_each
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function func) {
    while (first != last) {
        func(*first);
        ++first;
    }
    return func;
}
void myForeachFunc(int x) { cout << ' ' << x; }
template <class T> struct myForeachClass : public unary_function<T, T> {
    void operator()(const T& x) { cout << ' ' << x; }
    void print() { cout << "test foreach class"; }
};
// 12------replace
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& oldvalue,
             const T& newValue) {
    while (first != last) {
        if (*first == oldvalue)
            *first = newValue;
        ++first;
    }
}
// 13------replace_copy
template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
                            OutputIterator result, const T& oldvalue,
                            const T& newValue) {
    while (first != last) {
        *result = (*first == oldvalue) ? newValue : *first;
        ++first;
        ++result;
    }
    return result;
}
// 14------replace_if
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
                const T& newValue) {
    while (first != last) {
        if (pred(*first))
            *first = newValue;
        ++first;
    }
}
// 15-----count
template <class InputIterator, class T>
inline typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value) {
    typename iterator_traits<InputIterator>::difference_type cnt = 0;
    while (first != last) {
        if (*first == value)
            ++cnt;
        ++first;
    }
    return cnt;
}
// 16-----count_if
template <class InputIterator, class Predicate>
inline typename iterator_traits<InputIterator>::difference_type
count_if1(InputIterator first, InputIterator last, Predicate pred) {
    typename iterator_traits<InputIterator>::difference_type cnt = 0;
    while (first != last) {
        if (pred(*first))
            ++cnt;
        ++first;
    }
    return cnt;
}
// 17------find_if
template <class InputIterator, class Predicate>
inline InputIterator find(InputIterator first, InputIterator last,
                          Predicate pred) {
    while (first != last && !pred(*first)) {
        ++first;
    }
    return first;
}
// 18-----lower_bound
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& val) {
    ForwardIterator it;
    typename iterator_traits<ForwardIterator>::difference_type step = 0,
                                                               cnt = 0;
    cnt = YTQ::distance(first, last);
    while (cnt > 0) {
        it = first;
        step = cnt / 2;
        YTQ::advance(it, step);
        if (*it < val) {
            first = ++it;
            cnt -= step + 1;
        } else {
            cnt = step;
        }
    }
    return first;
}
// 19-----upper_bound
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                            const T& val) {
    ForwardIterator it;
    typename iterator_traits<ForwardIterator>::difference_type step = 0,
                                                               cnt = 0;
    cnt = YTQ::distance(first, last);
    while (cnt > 0) {
        it = first;
        step = cnt / 2;
        YTQ::advance(it, step);
        if (!(*it > val)) {
            first = ++it;
            cnt -= step + 1;
        } else {
            cnt = step;
        }
    }
    return first;
}
// 20-----bind1st
template <class Operation>
struct binder1st
    : public unary_function<typename Operation::second_argument_type,
                            typename Operation::result_type> {
    Operation op;
    typename Operation::first_argument_type value;
    binder1st(const Operation& p,
              const typename Operation::first_argument_type& v)
        : op(p), value(v) {}
    typename Operation::result_type
    operator()(const typename Operation::second_argument_type& x) {
        return op(value, x);
    }
};
template <class Operation, class T>
binder1st<Operation> bind1st(const Operation& fn, const T& x) {
    typedef typename Operation::first_argument_type arg1_type;
    return binder1st<Operation>(fn, arg1_type(x));
}
// 21----not1
template <class Predicate>
struct not1_negate : public unary_function<typename Predicate::argument_type,
                                           typename Predicate::result_type> {
    Predicate op;
    not1_negate(const Predicate& P) : op(P) {}
    typename Predicate::result_type
    operator()(typename Predicate::argument_type& x) {
        return !op(x);
    }
};
template <class Predicate> not1_negate<Predicate> not1(const Predicate& p) {
    return not1_negate<Predicate>(p);
}
// 22-----inserter
template <class Container>
class insert_iterator
    : public iterator<output_iterator_tag, void, void, void, void> {
  protected:
    Container* c;
    typename Container::iterator iter;

  public:
    insert_iterator(Container& x, typename Container::iterator i)
        : c(&x), iter(i) {}
    insert_iterator(const insert_iterator<Container>& x)
        : c(x.c), iter(x.iter) {}
    insert_iterator<Container>& operator*() { return *this; }
    insert_iterator<Container>&
    operator=(typename Container::const_reference x) {
        iter = c->insert(iter, x);
        ++iter;
        return *this;
    }
    insert_iterator<Container>& operator++() { return *this; }
    insert_iterator<Container>& operator++(int) { return *this; }
};
template <class Container, class Iterator>
insert_iterator<Container> inserter(Container& c, Iterator i) {
    return insert_iterator<Container>(c, typename Container::iterator(i));
}

// 23-----ostream_iterator
template <class Tp>
class ostream_iterator
    : public iterator<output_iterator_tag, void, void, void, void> {
  protected:
    ostream* out;
    const char* delim;

  public:
    ostream_iterator(ostream& x) : out(&x), delim(0) {}
    ostream_iterator(ostream& x, const char* c) : out(&x), delim(c) {}
    ostream_iterator<Tp>& operator=(const Tp& value) {
        *out << value;
        if (delim)
            *out << delim;
        return *this;
    }
    ostream_iterator<Tp>& operator*() { return *this; }
    ostream_iterator<Tp>& operator++() { return *this; }
    ostream_iterator<Tp>& operator++(int) { return *this; }
};

} // namespace YTQ

#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
// 1
template <class Container> void print(const Container& x, const string& name) {
    cout << name << " ";
    for (const auto& i : x) {
        cout << i << " ";
    }
    cout << endl;
}
void testAlgorithm() {

#if 0
    {
        cout << "1:inserter algorithm:" << endl;
        vector<int> bar, par;
        for (int i = 0; i != 5; ++i) {
            bar.push_back(i);
            par.push_back(i * 10);
        }

        print(bar, "bar");
        print(par, "par");

        vector<int>::iterator it = bar.begin();
        YTQ::advance(it, 3);

        ::copy(par.begin(), par.end(), YTQ::inserter(bar, it));
        print(bar, "bar1");
        print(par, "par1");

        int myins[] = {10, 20, 30, 40, 50, 60, 70};
        vector<int> myVec(5);
        copy(myins, myins + 7, myVec.begin());
        print(myVec, "myVec");
    }

    cout << "2:ostream_iterator algorithm:" << endl;

    std::vector<int> my;
    for (int i = 1; i != 11; ++i) {
        my.push_back(i);
    }
    print(my, "myVector");
    YTQ::ostream_iterator<int> out(std::cout, ",");
    std::copy(my.begin(), my.end(), out);
#endif
    cout<<"3:istream_iterator algorithm:"<<endl;

    std::vector<int> myvec;
    std::istream_iterator<int> ios1,iit1(std::cin);
    cout<<"input one numer:"<<endl;
    std::ostream_iterator<int> oit(std::cout,",");
    std::copy(iit1,ios1,oit);
}

// 0
using namespace std::placeholders;
double my_divide(double x, double y) { return x / y; }
struct MyPair {
    double a, b;
    double multiply() { return a * b; }
    double multiply2(int a) { return this->a * b * a; }
};

void testAlgorithm0() {

    std::vector<int> sv{10, 10, 10, 20, 20, 20, 20, 20, 30, 30};

    cout << "1:distance algorithm:";
    std::cout << YTQ::distance(sv.begin(), sv.end()) << endl;

    cout << "2:advance algorithm:";
    auto it = sv.begin();
    YTQ::advance(it, 3);
    cout << *it << endl;

    cout << "3:count_if algorithm:";
    auto cnt =
        YTQ::count_if(sv.begin(), sv.end(), not1(bind2nd(less<int>(), 4)));
    cout << cnt << endl;

    cout << "4:accumulate algorithm:";
    auto ret = YTQ::accumulate(sv.begin(), sv.end(), 100);
    cout << ret << "\t";
    ret = YTQ::accumulate(sv.begin(), sv.end(), 10, YTQ::myAccumulateFunc);
    cout << ret << "\t";
    ret = YTQ::accumulate(sv.begin(), sv.end(), 10, YTQ::myAccumulateClass());
    cout << ret << "\t";
    ret = YTQ::accumulate(sv.begin(), sv.end(), 100, YTQ::minus<int>());
    cout << ret << endl;
    cout << "5:foreach algorithm:";
    auto ret1 = YTQ::for_each(sv.begin(), sv.end(), YTQ::myForeachClass<int>());
    cout << endl;
    ret1.print();
    cout << endl;
    auto ret2 = YTQ::for_each(sv.begin(), sv.end(), YTQ::myForeachFunc);
    cout << endl;
    ret2(100);
    cout << endl;
    cout << "6:lower_bound or upper_bound:";
    auto ret3 = YTQ::lower_bound(sv.begin(), sv.end(), 20);
    cout << ret3 - sv.begin() << "\t";
    auto ret4 = YTQ::upper_bound(sv.begin(), sv.end(), 20);
    cout << ret4 - sv.begin() << "\t";
    auto ret5 = ::upper_bound(sv.begin(), sv.end(), 20);
    cout << ret5 - sv.begin() << endl;

    cout << "7: bind1st algorithm ";
    cout << YTQ::count_if(sv.begin(), sv.end(),
                          YTQ::not1(YTQ::bind1st(less<int>(), 10)));

    cout << "8:bind algorithm:" << endl;
    auto br = bind(my_divide, 10, 5);
    cout << "br:" << br() << endl;

    auto br1 = bind(my_divide, _1, 2);
    cout << "br1:" << br1(5) << endl;

    auto br2 = bind(my_divide, _2, _1);
    cout << "br2:" << br2(4, 2) << endl;

    auto br3 = bind<int>(my_divide, _1, _2);
    cout << "br3:" << br3(10, 3) << endl;
    MyPair ten{10, 2};

    auto br4 = bind<int>(&MyPair::multiply, _1);
    cout << "br4:" << br4(ten) << endl;

    auto br5 = bind<int>(&MyPair::a, _1);
    cout << "br5:" << br5(ten) << endl;

    auto br6 = bind<int>(&MyPair::b, ten);
    cout << "br6:" << br6(ten) << endl;

    auto br7 = bind(less<int>(), _1, 20);
    cout << "br7:" << count_if(sv.begin(), sv.end(), br7) << endl;

    auto br8 = bind(&MyPair::multiply2, _1, _2);
    cout << "br8:" << br8(ten, 3) << endl;
}